\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS254 Homework 5}
\newcommand{\myauthor}{Kevin Lewi}
\date{February 24, 2012}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 1}

Under the assumption, this means that the YES and NO instances of SAT can be 
distinguished with high probability, given only $o(\log n)$ bits of randomness 
and querying a constant number of positions in the proof.

Note that if we only use $o(\log n)$ bits of randomness, then there can only be 
$2^{o(\log n)}$ positions indexable in the proof by the machine. Thus, there 
must exist a proof that is only of length $2^{o(\log n)}$ that serves the same 
purpose. Note that $2^{o(\log n)}$ is sub-polynomial, and so if we already know 
that the proof must be so small, we can simply iterate over all such proofs of 
at most that length, deterministically, to find if there exists a proof which 
satisfies the requirements for a YES-instance. Otherwise, we output NO.

Thus, since we have shown the existence of a machine who, deterministically, is 
able to search for the existence of such a proof (since the proof length is not 
very long). Thus, SAT is in P. Since SAT is NP-complete, this implies that P = 
NP.

\section*{Problem 2}

Call this new problem $P$. We know from class that Set Cover is NP-hard to 
approximate by a constant factor. We will show a simple approximation-preserving 
reduction from Set Cover to $P$, such that if there exists a constant factor 
approximation to $P$, then there exists a constant factor approximation to Set 
Cover.

Given an instance $I$ of problem $P$, we construct an instance of Set Cover in 
the following manner: create a set $S_v$ for each vertex $v \in V$, where $S$ 
covers all vertices in $V$ that are incident to $v$, including $v$ itself. Thus, 
each set $S_v$ covers $N(v)$, including $v$. The elements of the Set Cover 
instance are just the vertices in the graph, so, the set of elements is simply 
$V$.

We have defined $|V|$ sets and $|V|$ elements. Now, suppose we have a constant 
factor approximation to the min-set-cover problem. Note that the set covers 
correspond in a one-to-one fashion with the set of all valid possibilities for 
$P$. The constant-factor approximation to min-set-cover would choose some subset 
$T$ of the collection of subsets $\{ S_v \}$ such that all elements are covered. 
Thus, we can use this subset as a solution for problem $P$. Thus, there can't 
exist such a constant-factor approximation unless P = NP.


\end{document}
